package codetop.microsoft.T679;

/**
 * @Author: 18362
 * @Create: 2022-09-06 22:51:18 星期二
 */
class Solution {

    private boolean valid;

    public boolean judgePoint24(int[] cards) {
        boolean[] visited = new boolean[cards.length];
        double[] newCards = new double[cards.length];
        for (int i = 0; i < cards.length; i++)
            newCards[i] = cards[i] * 1.0;
        dfs(newCards, visited, 0);
        return valid;
    }

    private void dfs(double[] cards, boolean[] visited, int used) {
        if (valid)
            return;
        if (used == cards.length-1) {
            double res = 0;
            for (int i=0; i<visited.length; ++i) {
                if (!visited[i]) {
                    res = cards[i];
                    break;
                }
            }
            if (Math.abs(res - 24) <= 0.00001)
                valid = true;
            return;
        }
        for (int i=0; i<cards.length; ++i) {
            if (visited[i])
                continue;
            for (int j=0; j<cards.length; ++j) {
                if (j == i || visited[j])
                    continue;
                visited[j] = true;
                double a = cards[i], b = cards[j];
                cards[i] = a + b;
                dfs(cards, visited, used+1);
                cards[i] = a - b;
                dfs(cards, visited, used+1);
                cards[i] = a * b;
                dfs(cards, visited, used+1);
                if (b != 0) {
                    cards[i] = a / b;
                    dfs(cards, visited, used+1);
                }
                cards[i] = a;
                visited[j] = false;
            }
        }
    }
}